package com.atguigu.sort;

import java.util.Random;

public class CountSort {
    /**
     * 非比较排序算法之排序算法
     * 验证计数排序算法的稳定性
     * 适用于排序的数据范围比较小的场景
     * 线性时间内对数据进行排序
     * @param args
     */

    public static void main(String[] args) {
        int n = 26 * 26 * 26 * 26;
        Student[] students = new Student[n];
        int k = 0;
        Random random = new Random();
        for (char c1 = 'a'; c1 <= 'z'; c1++) {
            for (char c2 = 'a'; c2 <= 'z'; c2++) {
                for (char c3 = 'a'; c3 <= 'z'; c3++) {
                    for (char c4 = 'a'; c4 <= 'z'; c4++) {
                        students[k] = new Student("" + c1 + c2 + c3 + c4, random.nextInt(101));
                        k++;
                    }
                }
            }
        }
        int R=101;

        int[] cnt = new int[R];
        for (Student student : students) {
            cnt[student.getScore()]++;          //O(N)
        }
        int[] index = new int[R + 1];
        for (int i = 0; i < R; i++) {
            index[i + 1] = index[i] + cnt[i];  //O(R)
        }
        Student[] temp = new Student[n];
        for (Student student : students) {
            temp[index[student.getScore()]] = student;   //O(N)
            index[student.getScore()]++;
        }
        System.arraycopy(temp, 0, students, 0, n);  //O(N)

        //总体时间复杂度：O(N+R)
        //N是数据规模，R是数据最大值
        //验证计数排序算法排序的正确性
        for (int i = 1; i < n; i++) {
            if (students[i].getScore() < students[i - 1].getScore()) {
                throw new IllegalArgumentException("Sort failed");
            }
            //验证计数排序算法的稳定性。
            if(students[i].getScore()==students[i-1].getScore()){
                if(students[i-1].getName().compareTo(students[i].getName())>0){
                    throw new IllegalArgumentException("Non-Stable counting sort!");
                }
            }
        }
    }
}
